#include <bits/stdc++.h>
using namespace std;

vector<int> getNext(string &pattern) {
  vector<int> next(pattern.size());

  int j = -1;

  for (int i = 0; i < pattern.size(); i++) {
    while (j >= 0 && pattern.at(i) != pattern.at(j + 1)) {
      j = next.at(j);
    }

    if (pattern.at(i) == pattern.at(j + 1)) {
      j++;
    }
    next.at(i) = j;
  }

  return next;
}
int strStr(string &text, string &pattern) {
  vector<int> next = getNext(pattern);

  int j = -1;
  for (int i = 0; i < text.size(); i++) {
    while (j >= 0 && pattern.at(j + 1) != text.at(i)) {
      j = next.at(j);
    }

    if (pattern.at(j + 1) == text.at(i)) {
      j++;
    }

    if (j == pattern.size() - 1) {
      return (i - pattern.size() + 1);
    }
  }
}